P2120 [ZJOI2007]仓库建设

did_i 为工厂 ii 到工厂 nn (山底)的距离, dpidp_i 为在第 ii 个工厂建仓库的最小花费。

因为只能向下运,所以第 nn 个工厂必须建仓库存放它自己的产品,答案便为 dpndp_n

边界条件 dp0dp_0 为不建仓库的花费。

那么有转移:

dpi=min{dpj(SumpiSumpj)di+ci}dp_i=\min\{dp_j-(Sump_i-Sump_j)d_i+c_i\}

dpi=min{dpj+Sumpjdi}Sumpidi+cidp_i=\min\{dp_j+Sump_jd_i\}-Sump_id_i+c_i

设有两决策点 j<kj<k , 且 jj 优于 kk

dpj+Sumpjdi<dpk+Sumpkdidp_j+Sump_jd_i <dp_k+Sump_kd_i

dpjdpk<(SumpjSumpk)didp_j-dp_k <-(Sump_j-Sump_k)d_i

注意到 did_i 是递减的,但 di-d_i 是递增的,所以正常维护一个下凸包就行了。

#include <cstdio>
#define LL long long

const int MAXN = 1e6;
int n , d[ MAXN + 5 ] , c[ MAXN + 5 ];
LL dp[ MAXN + 5 ] , p[ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;

LL fx( int i ) { return p[ i ]; }
LL fy( int i ) { return dp[ i ]; }
LL deltax( int i , int j ) { return fx( i ) - fx( j ); }
LL deltay( int i , int j ) { return fy( i ) - fy( j ); }

int main( ) {
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i ++ )
		scanf("%d %lld %d",&d[ i ],&p[ i ],&c[ i ]) , p[ i ] += p[ i - 1 ];
	for( int i = 1 ; i <= n ; i ++ ) d[ i ] = d[ n ] - d[ i ];
	
	for( int i = 1 ; i <= n ; i ++ ) dp[ 0 ] += d[ i ] * ( p[ i ] - p[ i - 1 ] );
	Head = 1 , Tail = 0; Que[ ++ Tail ] = 0;
	for( int i = 1 ; i <= n ; i ++ ) {
		for( ; Head < Tail && deltay( Que[ Head ] , Que[ Head + 1 ] ) >= -d[ i ] * deltax( Que[ Head ] , Que[ Head + 1 ] ) ; Head ++ );
		dp[ i ] = dp[ Que[ Head ] ] - ( p[ i ] - p[ Que[ Head ] ] ) * d[ i ] + c[ i ];
		for( ; Head < Tail && deltay( Que[ Tail - 1 ] , Que[ Tail ] ) * deltax( Que[ Tail ] , i ) >= deltay( Que[ Tail ] , i ) * deltax( Que[ Tail - 1 ] , Que[ Tail ] ) ; Tail -- );
		Que[ ++ Tail ] = i;
	}
	printf("%lld\n", dp[ n ] );
	return 0;
}